Нормальні форми БД

Кваліфікаційний мінімум (залік). Перевірка здатності студента записати визначення Бойса Кодда у вигляді одної з інтуіціоністичних логік, в даному випадку MLTT. Тестове завдання для мови Anders.

Визначення

Визначення 1. Функціональна залежність. Відобреження X → Y називається функціональним, якщо длоя кожного x ∊ X існує лише одне y ∊ Y. X називається доменом (областю визначення), а Y — кодоменом (областю значень).

Визначення 2. Скалярні типи. Наступні типи ми вважаємо скалярними: 1) типи натуральних чисел (GMP); 2) Неструктуровані бінарні дані (ізоморфно 1). 3) послідовні лічильники, сіквенси (BRIN індекси); 4) загальні індекси GUID (B-tree, LSM, PGM); 5) IEEE-754; 6) EBCDIC або аналоги Money, тощо.

Визначення 3. Векторні типи. Добуток X * Y ... називається кортежем. Синонім — вектор. Визначається натуральним числом N — кількістю елементів, N скалярними типами та N елементами типів.

Визначення 4. Вектори, елементи яких є тільки скалярними типами називаються елементарними векторами.

Визначення 5. Вектори, елементи яких можуть бути інші вектори називаються тензорами.

Визначення 6. Функціональна залежність f : X → Y, де домен X — вектор, а кодомен — скаляр, називається функціоналом.

Визначення 7. Ключі і атрибути. Якщо функціональна залежність X → Y має X та Y у вигляді типів векторів — то домен X називається складним ключем, а Y — атрибутами-колонками.

Визначення 8. Перша нормальна форма. Відображення X -> Y, де X, Y — або скаляри, або елементарні веткори називається першою нормальною формою.

Визначення 9. Друга нормальна форма. Відображення X -> Y називається другою нормальною формою, якщо воно одночасно є: 1) першою нормальноюд формою; 2) для кожного елементу Y[i] існує функціонал f[i] : X -> Y[i]; 3) не існує підмножини X[o] ⊂ X, яка б утворювала функціонал X[o] -> Y.

Визначення 10. Третя нормальна форма. Відображення X -> Y називається третьою нормальною формою, якшо воно одночасно є: 1) другою нормальною формою; 2) для будь яких i,j : N не існує функціональної залежності Y[i] -> Y[j], де Y[i],Y[j] ⊂ Y.

[1]. Erik Meijer and Gavin Bierman. A co-Relational Model of Data for Large Shared Data Banks. Microsoft Research. https://dl.acm.org/doi/pdf/10.1145/1952746.1961297.